Reliable communication over a network of packet erasure channels is a well-studied problem. Several solutions have been proposed, especially in the case when there is no feedback. One such solution is known as digital fountain codes. The digital fountain codes constitute a well-known approach to this problem. From a block of k transmit packets, the sender generates random linear combinations in such a way that the receiver can, with high probability, decode the block once it receives any set of slightly more than k linear combinations. This approach has low complexity and requires no feedback, except to signal successful decoding of the block.
Another known solution involves the use of random linear network coding. Random linear network coding was originally introduced for the case of error-free networks with specified link capacities, and was extended to the case of erasure networks. In contrast to fountain codes, the random linear network coding solution does not require decoding at intermediate nodes and can be applied in any network. Each node transmits a random linear combination of all coded packets it has received so far. This solution ensures that with high probability, the transmitted packet will have what is called the innovation guarantee property, i.e., it will be innovative to every receiver that receives it successfully, except if the receiver already knows as much as the sender. An innovative packet is a linear combination of packets which is linearly independent of previously received linear combinations, and thus conveys new information. Thus, every successful reception will bring a unit of new information. This scheme is shown to achieve capacity for the case of a multicast session.
Yet another known solution utilizes priority encoding transmission (PET). PET a works by proposing a code for the erasure channel that ensures that a receiver will receive the first (or highest priority) i messages using the first ki coded packets, where ki increases with decreasing priority. This is extended to systems that perform network coding. A concatenated network coding scheme is known which incorporates a delay-mitigating pre-coding stage. This scheme guarantees that the kth innovative reception will enable the receiver to decode the kth message. In such schemes however, the ability to decode messages in order requires a reduction in throughput because of the pre-coding stage.
Others have studied the queue stability and delay of block-based random linear coding versus uncoded Automatic Retry reQuest (ARQ) for stochastic arrivals in a broadcast setting. However, this work does not consider the combination of coding and feedback in one scheme. In still another related work, others have studies the case of load-dependent variable sized coding blocks with acknowledgements (ACKs) at the end of a block, using a bulk-service queue model. One of the differences in the present invention is that a receiver ACKs packets even before decoding them, and this enables the sender to perform online coding.
Online feedback-based adaptation of the code has been considered, and a coding scheme for the case of two receivers proposed. This work focuses on the maximum possible stable throughput, and does not consider the use feedback to minimize queue size or decoding delay. Still others have studied study the throughput of a block-based coding scheme, where receivers acknowledge the successful decoding of an entire block, allowing the sender to move to the next block. Next, they consider the option of adapting the code based on feedback for the multiple receiver case. They build on the two-receiver case and propose a greedy deterministic coding scheme that may not be throughput optimal, but picks a linear combination such that the number of receivers that immediately decode a packet is maximized. In contrast, embodiments of the present invention incorporate throughput-optimal policies that aim to minimize queue size and delay.
In other work an erasure coding algorithm called Tetrys has been proposed to ensure reliability in spite of losses on the acknowledgment path. While this scheme also employs coding in the presence of feedback, this approach is to make minimal use of the feedback, in order to be robust to feedback losses. As opposed to such an approach, the present invention uses the available feedback to improve the coding scheme and other performance metrics. For instance, in the earlier scheme, packets are acknowledged (if at all) only when they are decoded, and these are then dropped from the coding window.
However, by way of the present invention by dropping packets when they are seen, a smaller coding window is maintained without compromising on reliability and throughput. A packet is considered seen when the receiving node receives a linear combination including the packet and only subsequent packets, with respect to some fixed ordering on the original packet stream. A smaller coding window translates to lower encoding complexity and smaller queue size at the sender in the case of stochastic arrivals.
The use of ACKs and coded retransmissions in a packet erasure broadcast channel has been considered for multiple unicasts and multicast. The main goal of these works however, is to optimize the throughput. Other metrics such as queue management and decoding delay are not considered. In the present invention the focus is on using feedback to optimize these metrics as well, in addition to achieving 100% throughput in a multicast setting. The presently disclosed coding module is specified using the more general framework of seen packets, which allows the derivation of the drop-when-seen queue management algorithm and bring out the connection between the physical queue and virtual queue.